备用返回通道

转到题目

题目描述：

给定一个由 $n$ 个整数构成的数组 $a_1,a_2,\dots ,a_n$，我们称这个数组为“数独数组”，当且仅当其每个长度为 9 的连续子数组都包含数字 1 到 9。

现在，要求判断是否存在一种方案，可以通过重新排序数组使得数组成为数独数组。如果可以，则输出 “YES”；否则输出 “NO”。

输入描述：

• 第一行输入一个整数 $n$ ( $9\le n\le {10}^5$ )，代表数组的长度。
• 第二行输入 $n$ 个整数 $a_1,a_2,\dots ,a_n$ ( $1\le a_i\le 9$ )，代表数组中的元素。

输出描述：

• 如果数组在重新排序后可以成为数独数组，输出 “YES”；否则输出 “NO”。

示例 1：

输入：

9
1 2 3 4 5 6 7 9 8
复制代码

输出：

YES
复制代码

解释： 在这个示例中，数组已经满足数独数组的条件，不需要重新排序。

示例 2：

输入：

9
1 2 3 4 5 6 7 8 1
复制代码

输出：

NO
复制代码

解释： 这个数组不能通过重新排序变成数独数组，因为数字 1 出现了两次，而缺少了其他数字（例如 9）。

解析:

一定要仔细读题，不要着急。确定了之后再码。

思路引导

• 从 数独数组 的定义上来看,去剖析一个数独数组的 “结构” 然后寻找排序后，导致’这’的所有解.
  1. 要满足每个子数组的都要符合条件的:
  • 至少要满足，第一个长度为9的子数组是 ‘数独数组’
  • 在此之后 我们泛化，将这个数组变长,以找到所有 数独数组。
    • 我们把长度为9的数组向右拓展:开始是 [0:9:] 下一个是 [1:10:] 以此类推…
    • 可以观察到,新进来的元素一定要与离开的元素保持一致,这样就能保证构造永远符合’数独数组’的定义
      1. 我们找到了所有 解空间 的结构,下一步就是寻找 定义域
  • 经过 更变顺序 后,能不能让其可能存在于这个 解空间 呢,是否有性质可推出?
  • 因为我们知道了 解空间 的结构，因此可以推出部分性质.
    • 每个数都是每经过9个,出现一次
    • 等价地就是 他们9个数字的计数（cnt）一定是差距不过1的 我们记作条件C
    • 这样,我们找到了一个必要条件
    • 那它是不是充分条件呢？
      • 如果输入不满足条件C，肯定是NO
      • 如果是满足,我们就要细细考虑一下了
        • 我们发现，因为顺序是我们可以任意排布的，因此，C满足,我一定可以构造出这个数独数组
    • 因此得出结论:C是答案的充要条件
      1. 到这里解题就已经结束了,但这里补充一下:
  • 我为什么一定确定,需要的性质，可能在cnt上呢？
    • 因为我可以排序，因此我这个性质最好与顺序无关，因此我找计数性质，以便后续确定这个性质是不是充分的

      代码实现

python代码

n = int(input())

li = list(map(int,input().split()))
cnt = [0]*9
for i in li:
    cnt[i-1]+=1
if(max(cnt)-min(cnt) >1):
    print("NO")
else:
    print("YES")
复制代码

cpp

#include<bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
int n;
int cnt[9];
signed main(){
    cin>>n;
    int chace;
    int MAX = 0;
    int MIN = inf;
    while(n--){
        cin>>chace;
        cnt[chace-1]++;
    }
    for (int i = 0 ;i<9;i++){
        MAX = max(MAX,cnt[i]);
        MIN = min(MIN,cnt[i]);
    }
    if (MAX-MIN >1) cout<<"NO"<<endl;
    else cout<<"YES"<<endl;
    return 0;
}
复制代码